#include <stdlib.h>     /* srand, rand */
#include <iostream>
#include <time.h>       /* time */
#include <stack>
#include <sstream>
#include "BinaryTreeGenerator.hpp"

#ifdef GTEST
#include "gtest/gtest.h"
#endif

#define __DEBUG__(code) if (getenv("__DEBUG__")) code

namespace LEETCODE
{

std::string BinaryTreeNode::Show() {
    std::string result { };

    if (std::nullptr_t() == left.get()) {
        result += "NULL";
    } else {
        std::stringstream ss {};
        ss << left.get();
        result += ss.str();
    }

    result += " <- ";
    result += std::to_string(n);
    result += "(";
    std::stringstream ss {};
    ss << this;
    result += ss.str();
    result += ")";
    result += " -> ";

    if (std::nullptr_t() == right.get()) {
        result += "NULL";
    } else {
        std::stringstream ss {};
        ss << right.get();
        result += ss.str();
    }

    return result;
}

void BinaryTree::PreorderTraversal() {
    std::cout << "PreorderTraversal: ";

    std::shared_ptr<BinaryTreeNode> p { root };
    std::stack<std::shared_ptr<BinaryTreeNode>> nodeStack {};

    while (std::nullptr_t() != p.get() || !nodeStack.empty()) {
        if (std::nullptr_t() != p.get()) {
            std::cout << p->n << " -> ";
            nodeStack.push(p);
            p = p->left;
        } else {
            p = nodeStack.top()->right;
            nodeStack.pop();
        }
    }

    std::cout << std::endl;
}

void BinaryTree::InorderTraversal() {
    std::cout << "InorderTraversal: ";

    std::shared_ptr<BinaryTreeNode> p { root };
    std::stack<std::shared_ptr<BinaryTreeNode>> nodeStack {};

    while (std::nullptr_t() != p.get() || !nodeStack.empty()) {
        if (std::nullptr_t() != p.get()) {
            nodeStack.push(p);
            p = p->left;
        } else {
            p = nodeStack.top();
            std::cout << p->n << " -> ";
            nodeStack.pop();
            p = p->right;
        }
    }

    std::cout << std::endl;
}

void BinaryTree::PostorderTraversal() {
    std::cout << "PostorderTraversal: ";

    std::shared_ptr<BinaryTreeNode> p { std::nullptr_t() };
    std::shared_ptr<BinaryTreeNode> pre { root };
    std::stack<std::shared_ptr<BinaryTreeNode>> nodeStack {};
    nodeStack.push(root);

    while (!nodeStack.empty()) {
        p = nodeStack.top();
        if ((std::nullptr_t() == p->left && std::nullptr_t() == p->right) /* case 1: no left/right node */
         || (pre == p->left || pre == p->right)) {                        /* case 2: previous node is left/right node */
            std::cout << p->n << " -> ";
            nodeStack.pop();
            pre = p;
        } else {
            if (std::nullptr_t() != p->right) { /* right first */
                nodeStack.push(p->right);
            }
            if (std::nullptr_t() != p->left) { /* then left */
                nodeStack.push(p->left);
            }
        }
    }

    std::cout << std::endl;
}

enum class ACTID_E : std::uint32_t {
    ACT_TO_PARENT = 0U
  , ACT_TO_LEFT
  , ACT_TO_RIGHT
  , ACT_ADD_LEFT
  , ACT_ADD_RIGHT
};
std::string ACTID_E_str(ACTID_E const _act) {
    switch (_act) {
        case ACTID_E::ACT_TO_PARENT: return "TO_PARENT";
        case ACTID_E::ACT_TO_LEFT: return "TO_LEFT";
        case ACTID_E::ACT_TO_RIGHT: return "TO_RIGHT";
        case ACTID_E::ACT_ADD_LEFT: return "ADD_LEFT";
        case ACTID_E::ACT_ADD_RIGHT: return "ADD_RIGHT";
    }
    return "";
}

std::shared_ptr<BinaryTreeNode> addNode(std::shared_ptr<BinaryTreeNode> & _cur, std::shared_ptr<BinaryTreeNode> const & _new, ACTID_E const _actID) {
    static std::stack<std::shared_ptr<BinaryTreeNode>> nodeStack {};

#define IF_NULLPTR_RETURN_SELF(ptr) if (std::nullptr_t() == ptr.get()) { return _cur; } else { nodeStack.push(_cur); return ptr; }
#define IF_NULLPTR_ADD(ptr) if (std::nullptr_t() == ptr.get()) { ptr = _new; return std::nullptr_t(); } else { return _cur; }

    switch (_actID) {
        case ACTID_E::ACT_TO_PARENT:
            if (nodeStack.empty()) {
                return _cur;
            } else {
                std::shared_ptr<BinaryTreeNode> result { nodeStack.top() };
                nodeStack.pop();
                return result;
            }
        case ACTID_E::ACT_TO_LEFT:
            IF_NULLPTR_RETURN_SELF(_cur->left)
        case ACTID_E::ACT_TO_RIGHT:
            IF_NULLPTR_RETURN_SELF(_cur->right)
        case ACTID_E::ACT_ADD_LEFT:
            IF_NULLPTR_ADD(_cur->left)
        case ACTID_E::ACT_ADD_RIGHT:
            IF_NULLPTR_ADD(_cur->right)
        default:
            return _cur;
    }
}

std::shared_ptr<BinaryTree> BinaryTreeGenerator(std::uint64_t const _nodeNum) {
    if (_nodeNum < 1) {
        return std::nullptr_t();
    }

    srand(time(NULL));
    std::shared_ptr<BinaryTree> tree { std::make_shared<BinaryTree>() };
    std::shared_ptr<BinaryTreeNode> curNode { std::nullptr_t() };

    for (std::uint64_t i {0U}; i < _nodeNum; ++i) {
        std::shared_ptr<BinaryTreeNode> newNode { std::make_shared<BinaryTreeNode>() };
        newNode->n = rand() % 1000;

        if (std::nullptr_t() == tree->root.get()) {
            __DEBUG__(std::endl(std::cout << " root: " << newNode->Show()));
            tree->root = newNode;
        } else {
            /* choose an action:
             * 0 - move to the parent node;
             * 1 - move to the left node;
             * 2 - move to the right node;
             * 3 - add to the left node;
             * 4 - add to the right node;
             */
            curNode = tree->root;
            while (1) {
                ACTID_E actID { static_cast<ACTID_E>(rand() % 5) };
                __DEBUG__(std::cout << "Act: " << ACTID_E_str(actID) << " node: " << curNode->Show());
                __DEBUG__(std::cout << " new node: " << newNode->Show() << std::endl);
                curNode = addNode(curNode, newNode, actID);
                if (std::nullptr_t() == curNode.get()) {
                    break;
                }
            }
        }
    }

    return tree;
}

#ifdef GTEST
TEST(TestBinaryTreeGenerator, TestGenerateRoot) {
    std::shared_ptr<BinaryTree> tree { BinaryTreeGenerator(10) };
    tree->PreorderTraversal();
    tree->InorderTraversal();
    tree->PostorderTraversal();
    ASSERT_TRUE(std::nullptr_t() != tree->root.get());
    ASSERT_TRUE(std::nullptr_t() != tree->root->left.get() || std::nullptr_t() != tree->root->right.get());
}

#endif




}
